/*
Detail: The block pointer for an allocated block points to the start
of user data (just after the header of the block). However,
for free blocks, the block pointer points to the very start
of the free block.
*/


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "Vector Strike Force Delta",
    /* First member's full name */
    "Aaron Drew Lane",
    /* First member's email address */
    "aaron.lane@utoronto.ca",
    /* Second member's full name (leave blank if none) */
    "Alex Litoiu",
    /* Second member's email address (leave blank if none) */
    "alex.litoiu@utoronto.ca"
};

/*************************************************************************
 * Basic Constants and Macros
 * You are not required to use these macros but may find them helpful.
*************************************************************************/
#define WSIZE       4            /* word size (bytes) */
#define DSIZE       8            /* doubleword size (bytes) */
#define CHUNKSIZE   (1<<7)      /* initial heap size (bytes) */
#define OVERHEAD    8            /* overhead of header and footer (bytes) */
#define FBSIZE      16          /*minimum size of a free block in bytes*/

#define MAX(x,y) ((x) > (y)?(x) :(y))

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))

/* Read and write a word at address p */
#define GET(p)          (*(size_t *)(p))
#define PUT(p,val)      (*(size_t *)(p) = ((size_t)val))

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)     (GET(p) & ~0x7)
#define GET_ALLOC(p)    (GET(p) & 0x1)

/* Given block ptr bp, compute address of its header and footer */
#define A_HDRP(bp)        ((char *)(bp) - WSIZE)
#define A_FTRP(bp)        ((char *)(bp) + GET_SIZE(A_HDRP(bp)) - DSIZE)

/* Given an allocated block ptr bp, compute address of next and previous blocks */
#define A_NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define A_PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

/* Given a free block ptr bp, return the address of the next and prev pointers */
#define F_NP(bp) ((char *)(bp) + DSIZE)
#define F_PP(bp) ((char *)(bp) + WSIZE)

/* Given a free block ptr bp, compute address of next and previous blocks */
#define F_NEXT_BLKP(bp) ((char*)*(size_t*)(F_NP(bp)))
#define F_PREV_BLKP(bp) ((char*)*(size_t*)(F_PP(bp)))

/* Given a free block ptr bp, return whether it has a next / prev */
#define F_HAS_NEXT(bp) ((void *)F_NEXT_BLKP(bp)!=NULL)
#define F_HAS_PREV(bp) ((void *)F_PREV_BLKP(bp)!=NULL)

/* Given a header pointer of a free block, return the address of its header */
#define F_FTRP(bp) ((char *)(bp) + GET_SIZE(bp) - WSIZE)

/* Convert to and from free_style bp and allocated_style bps */
#define F_TO_A(bp) ((char *)(bp) + WSIZE)
#define A_TO_F(bp) ((char *)(bp) - WSIZE)

/* Struct representing a minimum_sized_free_block. The way the internal variables of the block
are contained corresponds to a free block. Each allocated block must be at least
as big as the free block. The internal variables are never actually used. Instead,
macros are used to operate, even on free blocks */
typedef struct{
    int header;
    int prev_ptr;
    int next_ptr;
    //empty space would go here
    int footer;
    }min_free_block;

//If the prev_ptr value is NULL, then we know it's the head. Never consume
//it if so
min_free_block header;
void *flist_head = &header;
void *heap_start = NULL;


void print_all(){
    printf("\n");

    printf("Address of flist_head: %p\n", flist_head);
    printf("flist_head next: %p\n", F_NEXT_BLKP(flist_head));

    printf("\n");

    void * ptr = heap_start;

    int freecount = 0;
    int alloccount = 0;
    for (ptr = heap_start; GET_SIZE(ptr)!=0; ptr+=GET_SIZE(ptr))
    {
        int freealloc = GET_ALLOC(ptr);
        if (freealloc){
            printf("ALLOC BLOCK %d\n",freecount++);
            printf("Address: %p\n", ptr);
        }else{
            printf("FREE BLOCK %d\n",alloccount++);
            printf("Next: %p\n",F_NEXT_BLKP(ptr));
            printf("Prev: %p\n",F_PREV_BLKP(ptr));
            printf("Address: %p\n", ptr);
        }

        printf("Size: %d\n", GET_SIZE(ptr));
        printf("\n");
    }
}

/**********************************************************
 * add_to_free_list
 * Takes in a free_style bp. Adds the free block to the
 * free list
 **********************************************************/
void add_to_free_list(void *bp)
{
    void *first = F_NEXT_BLKP(flist_head); 

    //insert at the start of the list
    //set nexts
    PUT(F_NP(flist_head), bp);      //make head point to bp

    PUT(F_NP(bp), first);           //make bp point to what head used
                                    //to point to

    //set prevs

    //Set bp's next's prev to bp
    if(F_HAS_NEXT(bp))
        PUT(F_PP(F_NEXT_BLKP(bp)),bp);

    //set bp's prev to head
    PUT(F_PP(bp),flist_head);    
}

/**********************************************************
 * mm_init
 * Initialize the heap, including "allocation" of the
 * prologue and epilogue
 **********************************************************/
int mm_init(void) {
    if ((heap_start = mem_sbrk(4*WSIZE)) == NULL) {
        return -1;
    }

    PUT(heap_start, 0);                         // alignment padding 
    PUT(heap_start+WSIZE, PACK(OVERHEAD, 1));   // prologue header
    PUT(heap_start+DSIZE, PACK(OVERHEAD, 1));   // prologue footer
    PUT(heap_start+WSIZE+DSIZE, PACK(0, 1));    // epilogue header
    heap_start += WSIZE; 

    //Initialize flist_head
    PUT(flist_head, PACK(FBSIZE, 0));   //header
    PUT(F_PP(flist_head), NULL);        //prev pointer
    PUT(F_NP(flist_head), NULL);        //next pointer
    PUT(F_FTRP(flist_head), PACK(FBSIZE, 0));   //footer
    return 0;
}
 
/**********************************************************
 * coalesce
 * Covers the 4 cases discussed in the text:
 * - both neighbours are allocated
 * - the next block is available for coalescing
 * - the previous block is available for coalescing
 * - both neighbours are available for coalescing
 *
 * Coalesce also adds the free block somewhere in the free list
 * (near the coalesced sections or to the start)
 **********************************************************/
//takes in an allocated_style block pointer, and 
//returns an allocated_style block pointer
void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(A_FTRP(A_PREV_BLKP(bp)));
    size_t next_alloc = GET_ALLOC(A_HDRP(A_NEXT_BLKP(bp)));
    size_t size = GET_SIZE(A_HDRP(bp));

    void *bpf = A_TO_F(bp);
    if (prev_alloc && next_alloc) {       /* Case 1 */
        add_to_free_list(bpf);

        return bp;
    }

    else if (prev_alloc && !next_alloc) { /* Case 2 */
        /* A pointer to the next block, which is free*/
        void * nextf = A_HDRP(A_NEXT_BLKP(bp));//trick usage of A_HDRP
        void * nexts_prevf = F_PREV_BLKP(nextf);
        void * nexts_nextf = F_NEXT_BLKP(nextf);
        
        //coalesce this block with the next block
        PUT(F_NP(nexts_prevf),bpf);    //point next's prev's next to it
        if (nexts_nextf!=NULL)
            PUT(F_PP(nexts_nextf), bpf);    //point next's next's prev to it
        PUT(F_NP(bpf), nexts_nextf);    //point its next pointer to next's next
        PUT(F_PP(bpf), nexts_prevf);    //point its prev pointer to next's prev
        
        //set sizes
        size_t next_size = GET_SIZE(nextf);
        size += next_size;
        PUT(A_HDRP(bp), PACK(size, 0));
        //since the size has been updated, this is now the footer 
        //of the new, large block
        PUT(A_FTRP(bp), PACK(size, 0)); 
        return (bp);
    }

    else if (!prev_alloc && next_alloc) { /* Case 3 */
        //no pointer changes must be made

        //prevf will never be the head pointer
        //void * prevf = A_HDRP(A_PREV_BLKP(bp)); //trick usage of A macros
        //void * prevs_nextf = F_NEXT_BLKP(prevf);
        //void * prevs_prevf = F_PREV_BLKP(prevf);

        //set sizes
        size += GET_SIZE(A_HDRP(A_PREV_BLKP(bp)));
        PUT(A_FTRP(bp), PACK(size, 0));
        PUT(A_HDRP(A_PREV_BLKP(bp)), PACK(size, 0));
        return (A_PREV_BLKP(bp));
    }

    else {            /* Case 4 */
        void * nextf = A_HDRP(A_NEXT_BLKP(bp)); //trick usage of A macros
        void * nexts_nextf = F_NEXT_BLKP(nextf);
        void * nexts_prevf = F_PREV_BLKP(nextf);

        PUT(F_NP(nexts_prevf),nexts_nextf);
        if (nexts_nextf != NULL)
            PUT(F_PP(nexts_nextf),nexts_prevf);

        size += GET_SIZE(A_HDRP(A_PREV_BLKP(bp)))  +
            GET_SIZE(A_FTRP(A_NEXT_BLKP(bp)))  ;
        PUT(A_HDRP(A_PREV_BLKP(bp)), PACK(size,0));
        PUT(A_FTRP(A_NEXT_BLKP(bp)), PACK(size,0));
        return (A_PREV_BLKP(bp));
    }

}

/**********************************************************
 * extend_heap
 * Extend the heap by "words" words, maintaining alignment
 * requirements of course. Free the former epilogue block
 * and reallocate its new header.
 **********************************************************/
 //Returns a free_style block pointer
void *extend_heap(size_t words)
{
    char *bp; 
    size_t size;

    /* Allocate an even number of words to maintain alignments */
    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;
    if ( (bp = mem_sbrk(size)) == NULL )
        return NULL;

    /* Initialize free block header/footer and the epilogue header */
    PUT(A_HDRP(bp), PACK(size, 0));                // free block header
    PUT(A_FTRP(bp), PACK(size, 0));                // free block footer
    PUT(A_HDRP(A_NEXT_BLKP(bp)), PACK(0, 1));        // new epilogue header

    /* Coalesce if the previous block was free */
    return A_TO_F(coalesce(bp));
}



void * first_fit(size_t asize) {
    void *bp; //free style pointer

    //If there are no free blocks at all, return NULL
    if (!F_HAS_NEXT(flist_head))
        return NULL;

    for (bp = F_NEXT_BLKP(flist_head); bp != NULL; bp = F_NEXT_BLKP(bp)) {
        if (!GET_ALLOC(bp) && (asize <= GET_SIZE(bp))) {
            return bp;
        }
    }
    return NULL;
}
void * best_fit(size_t asize) {
  int best_size = 0;
  int size;
  void * bp; //free style pointer
  void * best_ptr = NULL;

  //If there are no free blocks at all, return NULL
  if (!F_HAS_NEXT(flist_head)) {

    return NULL;
  }
  
  for (bp = F_NEXT_BLKP(flist_head); bp != NULL; bp = F_NEXT_BLKP(bp)) {
    assert(!GET_ALLOC(bp));

    size = GET_SIZE(bp);

    if ((asize <= size) && (best_size == 0 || size < best_size)) {
      best_size = size;
      best_ptr = bp;
      
      if (best_size == asize) {
        break;
      }
    }
  }

  return best_ptr;
}

/**********************************************************
 * find_fit
 * Traverse the free list searching for the first good fit
 * Return NULL if no free blocks can handle that size
 * Assumed that asize is aligned
 **********************************************************/
void * find_fit(size_t asize){
    return best_fit(asize);
}

/**********************************************************
 * place
 * Convert a free block into an allocated one. Does
 * the job of allocating a pre-existing free block
 **********************************************************/
//bp is the start of the block, in the free block style
void place(void* bp, size_t asize) {
    
    void* bpa = F_TO_A(bp);

    /* Get the current block size */
    size_t bsize = GET_SIZE(A_HDRP(bpa));

    //Fragment
    if (bsize-asize>=16){

        void * prev = F_PREV_BLKP(bp);
        void * next = F_NEXT_BLKP(bp);

        //place block
        PUT(A_HDRP(bpa), PACK(asize, 1));
        PUT(A_FTRP(bpa), PACK(asize, 1));

        //place extra free space
        int extra = bsize-asize;
        void * extra_header = A_FTRP(bpa)+WSIZE;
        void * extra_footer = extra_header + extra - WSIZE;
        PUT(extra_header, PACK(extra,0));
        PUT(extra_footer, PACK(extra,0));

        PUT(A_HDRP(bpa), PACK(asize, 1));
        PUT(A_FTRP(bpa), PACK(asize, 1));

        //remove from list
        PUT(F_NP(prev), extra_header);
        PUT(F_PP(extra_header), prev);

        PUT(F_NP(extra_header), next);
        if(next!=NULL)
            PUT(F_PP(next), extra_header);

    //Don't fragment
    }else{
        void * prev = F_PREV_BLKP(bp);
        void * next = F_NEXT_BLKP(bp);

        //remove from list
        PUT(F_NP(prev), next);

        if(next!=NULL)
            PUT(F_PP(next), prev);

        PUT(A_HDRP(bpa), PACK(bsize, 1));
        PUT(A_FTRP(bpa), PACK(bsize, 1));

    }

}

/**********************************************************
 * mm_free
 * Free the block and coalesce with neighbouring blocks
 **********************************************************/
//bp is an allocated_style bp
void mm_free(void *bp) {
  size_t size = GET_SIZE(A_HDRP(bp));
  PUT(A_HDRP(bp), PACK(size,0));
  PUT(A_FTRP(bp), PACK(size,0));
  coalesce(bp);
}


/**********************************************************
 * mm_malloc
 * Allocate a block of size bytes.
 * The type of search is determined by find_fit
 * The decision of splitting the block, or not is determined
 *   in place(..)
 * If no block satisfies the request, the heap is extended
 **********************************************************/
void *mm_malloc(size_t size) {
    //Throughout this function, bp is the start of the block,
    //as with all free blocks
    size_t asize; /* adjusted block size */
    size_t extendsize; /* amount to extend heap if no fit */
    char * bp;
    
    /* Ignore spurious requests */
    if (size <= 0)
        return NULL;

    /* Adjust block size to include overhead and alignment reqs. */
    if (size <= DSIZE)
        asize = DSIZE + OVERHEAD;
    else
        asize = DSIZE * ((size + (OVERHEAD) + (DSIZE-1))/ DSIZE);

    /* Search the free list for a fit */
    if ((bp = find_fit(asize)) != NULL) {
        place(bp, asize);
        //bp is free_style
        return (void*)F_TO_A(bp);
    }
    
    /* No fit found. Get more memory and place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
        return NULL;
    //print_all();
    place(bp, asize);
    //bp is free_style
    return (void*)F_TO_A(bp);
}

/**********************************************************
 * mm_realloc
 *********************************************************/
void *mm_realloc(void *ptr, size_t size) {
  void *oldptr = ptr;
  void *newptr;
  size_t copySize;
  
    copySize = GET_SIZE(A_HDRP(oldptr));
    
    //if there is adjacent space, attach the adjacent block

    void * next_headerf = A_HDRP(A_NEXT_BLKP(oldptr));

    if (!GET_ALLOC(next_headerf)){

        void * next_prevf = F_PREV_BLKP(next_headerf);
        void * next_nextf = F_NEXT_BLKP(next_headerf);

        size_t next_size = GET_SIZE(next_headerf);
        size_t available = copySize+next_size;

        printf("copySize: %u next_size:%u\n",copySize,next_size);
        printf("available: %u size+16:%u\n",available,size+16);
        if (available >= (size+16))
        {
            printf("size:%u\n",size);
            printf("FIRST PART\n");
            printf("oldptrf:%u +size(oldptr):%u =  next_headerf:%u\n",A_TO_F(oldptr),copySize, next_headerf);
            printf("A_FTRP(oldptr):%u\n",A_FTRP(oldptr));

            void *new_free = A_FTRP(oldptr)+4;
            size_t new_free_size = (available - size);

            if (size < copySize /*|| (ptr + size) >= mem_heap_hi() || (new_free+new_free_size)>=mem_heap_hi()*/)
                goto outside;
                printf("size:%d<copySize:%d;\n",size,copySize);

            //make new allocated block
            PUT(A_HDRP(oldptr),PACK(size,1));
            PUT(A_FTRP(oldptr),PACK(size,1));

            // make new free block
            PUT(new_free, PACK(new_free_size,0));
            PUT(F_NP(new_free), next_nextf);
            PUT(F_PP(new_free), next_prevf);
            PUT(F_FTRP(new_free), PACK(new_free_size,0));

            PUT(F_NP(next_prevf), new_free);
            if (next_nextf!=NULL)
                PUT(F_PP(next_nextf), new_free);

            printf("new_free:%u\n",new_free);
            printf("F_FTRP(new_free):%u\n",F_FTRP(new_free));
            printf("new_free+new_free_size-4:%u\n",new_free+new_free_size-4);
            printf("HEAP MAX:%u\n",mem_heap_hi());
            return oldptr;
        }
    }
    outside:
    printf("SECOND PART\n") ;

    //if there isn't adjacent space, do the inefficient way
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    

    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

/*******************************************************************************
 * mm_check()
 * Scans the heap and checks it for consistency.
 * Returns 1 if the heap is consistent, 0 if a case fails.
 ******************************************************************************/
//TODO add check on header and footer addresses being divisible by 8.
//TODO add macros for repeated calculations.
//FIXME lazy variable logic.
int mm_check() {
  int flag = 0;
  size_t cursize, size;
  char * bp, * next, * prev, * invalid;

  prev = flist_head;

  for (bp = F_NEXT_BLKP(flist_head); bp != NULL; bp = F_NEXT_BLKP(bp)) {
    /* Case: is every block in the free list marked as free? */
    if (GET_ALLOC(bp)) {
      printf("mm_check: found allocated block in the free list: %p\n", bp);

      return 0;
    } 
    
    if (F_HAS_NEXT(bp)) {
      next = F_NEXT_BLKP(bp);
      /* Case: are there any contiguous free blocks that escaped coalescing? */
      if (next == F_FTRP(bp) + WSIZE || next == bp - FBSIZE) {
        printf("mm_check: found contiguous free blocks in the free list: %p and \
            %p\n", bp, next);

        return 0;
      }
    } 

    /* Case: do the previous pointers in the free list point to the correct 
     * blocks? */
    if (F_PREV_BLKP(bp) != prev) {
      invalid = F_PREV_BLKP(bp);
      printf("mm_check: found invalid previous pointer in the free list: %p to \
             %p instead of %p.\n", bp, invalid, prev);

      return 0;
    }

    prev = bp;
  }

  for (invalid = heap_start; invalid != NULL; invalid += GET_SIZE(bp)) {
    /* Case: do all header and footer pairs match? */
    cursize = GET_SIZE(invalid);

    if (cursize != GET_SIZE(invalid + cursize - WSIZE)) {
      printf("mm_check: found mismatched header and footer: %p and %p\n", 
             invalid, invalid + cursize - WSIZE);

      return 0;
    }

    /* Case: is every free block in the free list? */
    if (!GET_ALLOC(invalid)) {   
      for (bp = F_NEXT_BLKP(flist_head); bp != NULL; bp = F_NEXT_BLKP(bp)) { 
        if (invalid == bp) {
          flag = 1;

          break;
        }
      }

      if (!flag) {
        printf("mm_check: found free block missing from the free list: %p\n", 
               invalid);

        return 0;
      }
    /* Case: do any allocated blocks overlap? */
    } else {
      if (invalid != heap_start) {
        size = GET_SIZE(invalid - WSIZE);
  
        if (size != GET_SIZE(invalid - size)) {
          printf("mm_check: found allocated block overlap: before %p, %p and %p \
                don't agree on size\n", invalid, invalid - size, 
                invalid - WSIZE);
  
          return 0;
        }
      }

      size = GET_SIZE(invalid + cursize);
 
      if (size != GET_SIZE(invalid + cursize + size - WSIZE)) {
        printf("mm_check: found allocated block overlap: after %p, %p and %p \
               don't agree on size\n", invalid, invalid + cursize, 
               invalid + cursize + size - WSIZE);
 
        return 0;
      }
    }
  }

  /* The heap is consistent, so return nonzero. */
  return 1;
}
